package com.dream.algoritm;

// 现在数据库有一张表，用来存储一个多叉树，id为主键，pid 表示父节点的 id，已知 "-1" 表示根节点，
// 现在要求打印出从根节点到每个子节点的路径（可以是无序的）。
//
// | id      | pid    |
// |---------|--------|
// | "A"     | "-1"   |
// | "A-1"   | "A"    |
// | "A-2"   | "A"    |
// | "A-3"   | "A"    |
// | "A-2-1" | "A-2"  |
// | "A-2-2" | "A-2"  |
// | "A-2-3" | "A-2"  |
//
// Input: [
//   {
//       "id": "A",
//       "pid": "-1"
//   },
//   {
//       "id": "A-1",
//       "pid": "A"
//   },
//   {
//       "id": "A-2",
//       "pid": "A"
//   },
//   {
//       "id": "A-3",
//       "pid": "A"
//   },
//   {
//       "id": "A-2-1",
//       "pid": "A-2"
//   },
//   {
//       "id": "A-2-2",
//       "pid": "A-2"
//   },
//   {
//       "id": "A-2-3",
//       "pid": "A-2"
//   }
// ]
// Output: [
//   "/A",
//   "/A/A-1",
//   "/A/A-2",
//   "/A/A-3",
//   "/A/A-2/A-2-1",
//   "/A/A-2/A-2-2",
//   "/A/A-2/A-2-3",
// ]

import java.util.*;

class Node {
    Node(String ID, String PID) {
        this.ID = ID;
        this.PID = PID;
    }
    public String ID; // 节点ID
    public String PID; // 父节点ID
}

public class Test2 {

    private static final String ROOT = "-1";
    public static void main(String[] args) {
        List<Node> nodes = new ArrayList<>();
        nodes.add(new Node("A", "-1"));
        // nodes.add(new Node("B", "-1"));
        nodes.add(new Node("A-1", "A"));
        nodes.add(new Node("A-2", "A"));
        nodes.add(new Node("A-3", "A"));
        nodes.add(new Node("A-2-1", "A-2"));
        nodes.add(new Node("A-2-2", "A-2"));
        nodes.add(new Node("A-2-3", "A-2"));
        nodes.add(new Node("A-2-4", "A-2"));

        process(nodes);
    }

    public static void process(List<Node> nodes) {
        Map<String, String> m = new LinkedHashMap<>();
        for (Node n: nodes) {
            m.put(n.ID, n.PID);
        }

        for (Map.Entry<String, String> e : m.entrySet()) {
            String k = e.getKey();
            String v = e.getValue();
            String r = "/" + k;
            while (!ROOT.equals(v)) {
                r = "/" + v + r;
                v = m.get(v);
            }
            System.out.println(r);
        }
    }
}